package com.shm.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author: shm
 * @dateTime: 2020/10/18 10:36
 * @description: 5543. 两个相同字符之间的最长子字符串 显示英文描述
 * 通过的用户数438
 * 尝试过的用户数547
 * 用户总通过次数438
 * 用户总提交次数629
 * 题目难度Easy
 * 给你一个字符串 s，请你返回 两个相同字符之间的最长子字符串的长度 ，计算长度时不含这两个字符。如果不存在这样的子字符串，返回 -1 。
 *
 * 子字符串 是字符串中的一个连续字符序列。
 *
 *
 *
 * 示例 1：
 *
 * 输入：s = "aa"
 * 输出：0
 * 解释：最优的子字符串是两个 'a' 之间的空子字符串。
 * 示例 2：
 *
 * 输入：s = "abca"
 * 输出：2
 * 解释：最优的子字符串是 "bc" 。
 * 示例 3：
 *
 * 输入：s = "cbzxy"
 * 输出：-1
 * 解释：s 中不存在出现出现两次的字符，所以返回 -1 。
 * 示例 4：
 *
 * 输入：s = "cabbac"
 * 输出：4
 * 解释：最优的子字符串是 "abba" ，其他的非最优解包括 "bb" 和 "" 。
 *
 *
 * 提示：
 *
 * 1 <= s.length <= 300
 * s 只含小写英文字母
 */
public class MaxLengthBetweenEqualCharacters {
    public int maxLengthBetweenEqualCharacters(String s) {
        List<List<Integer>> lists = new ArrayList<>();
        for (int i = 0; i < 26; i++) {
            lists.add(new ArrayList<>());
        }
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            int k = c - 'a';
            lists.get(k).add(i);
        }
        int ans = 0;
        for (List<Integer> list : lists) {
            if (list.size()>1){
                ans = Math.max(ans,list.get(list.size()-1)-list.get(0));
            }
        }
        return ans;
    }
}
